package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

import java.util.LinkedList;

public class MinDepth {
    //求二叉树的最小深度
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算左子树的深度
        int left = minDepth(root.left);
        // 计算右子树的深度
        int right = minDepth(root.right);
        // 如果左子树或右子树的深度不为 0，即存在一个子树，那么当前子树的最小深度就是该子树的深度+1
        // 如果左子树和右子树的深度都不为 0，即左右子树都存在，那么当前子树的最小深度就是它们较小值+1
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }
    public int minDepthBFS(TreeNode root) {
        if (root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while (!queue.isEmpty()){
            for (int i = queue.size(); i > 0 ; i--) {
                TreeNode node = queue.poll();
                if (node.left==null && node.right==null) return depth;
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
            }
            depth+=1;
        }
        return depth;
    }

    //求二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1+Math.max(left,right);
    }


    public static void main(String[] args) {
        MinDepth Main = new MinDepth();
        TreeNode left11 = new TreeNode(3);
        TreeNode left1 = new TreeNode(1,left11,null);
        TreeNode right1 = new TreeNode(4);
        TreeNode root = new TreeNode(0,left1,right1);
        System.out.println(Main.minDepthBFS(root));

    }
}
